import java.util.*;

public class 字符串的全部子序列 {
    //
    //递归 + 哈希去重
    public static Set<String> set;
    public static StringBuilder sb;
    public static int n;
    public String[] generatePermutation (String s) {
        // write code here
        n = s.length();
        set = new HashSet<>();
        sb = new StringBuilder();
        dfs(0,s);
        //第一次知道这样遍历
        String[] ret = new String[set.size()];
        int i = 0;
        for(String str : set){
            ret[i++] = str;
        }
        return ret;
    }

    public void dfs(int pos,String s){
        if(pos == n){
            set.add(sb.toString());
            return;
        }
        sb.append(s.charAt(pos));
        dfs(pos + 1,s);
        sb.deleteCharAt(sb.length() - 1);
        dfs(pos + 1,s);
    }
}
